import java.util.Random;



/**
 * Created with IntelliJ IDEA.
 * @author  rybak
 * Date: 10/31/13
 */
public class InsertionSort {

    /**
     *
     * @param length array
     * @return falling array
     */
    public int[] fillingArray(int length)
    {
        int [] arrayResalt = new int[length+1];
        for (int i=0;i<=length;i=i+1)
            arrayResalt[i]=length-i;

        return arrayResalt;
    }

    /**
     *
     * @param arrayForMix - this array will be mixed
     */
    public void mixingArray(int[] arrayForMix)
    {
        Random r = new Random();
        int lenghtArray = arrayForMix.length+1;
        int yd,xs;
        for (int i=0;i<=lenghtArray;i=i+1) {
            yd=arrayForMix[i];
            xs=r.nextInt(lenghtArray+1);
            arrayForMix[i]=arrayForMix[xs];
            arrayForMix[xs]=yd;
        }
    }

    /**
     *
     * @see
     * @param m - array for sorting
     * @return array sorted the method inserts
     * @throws
     */
    public int[] insertionSort(int[] m) {
        int t;
        int i, j;
        for (i = 0; i < m.length; i++) {
            t = m[i];
            for (j = i - 1; j >= 0 && m[j] > t; j--)
                m[j + 1] = m[j];

            m[j + 1] = t;
        }

        return m;
    }


    public Integer inmut(final Integer a)
    {
        a = 10;
        return a;
    }
    public static void main(String[] args) {
        int N=10;
        int arrayForSort[];

        InsertionSort classSort = new InsertionSort();


        arrayForSort = classSort.fillingArray(N);

        classSort.mixingArray(arrayForSort);

        System.out.println("\nAfter randomization\n");
        for (int i=0;i<=N;i=i+1)
            System.out.print(arrayForSort[i]+" ");


        long start, end;
        start=System.nanoTime();
        classSort.insertionSort(arrayForSort);
        end=System.nanoTime();

        System.out.println("\nBefore sorting\n");
        for (int i=0;i<=N;i=i+1)
            System.out.print(arrayForSort[i]+" ");

        System.out.print("time taken" + (end-start));

    }
}
